#include <iostream>

using namespace std;

// problem 1 to problem 3 skipped.

template<typename T>
struct Node {
  T _data;
  Node* _next;

  Node(T val) : _data(val), _next(NULL) {}
};

template<typename T>
void prepend(Node<T>*& head, T val) {
  Node<T>* p = new Node<T>(val);
  p->_next = head;
  head = p;
}

template<typename T>
void print_list(Node<T>* head) {
  while (head) {
    cout << head->_data << " ";
    head = head->_next;
  }
  cout << endl;
}

template<typename T>
void free_list(Node<T>* head) {
  while (head) {
    Node<T>* p = head;
    head = head->_next;
    delete p;
  }
}

// problem 4
template<typename T>
Node<T>* add(Node<T>* m, Node<T>* n, int carry) {
  if (!m && !n)
    return NULL;

  Node<T>* l = new Node<T>(carry);
  if (m) 
    l->_data += m->_data;
  if (n) 
    l->_data += n->_data;
  
  carry = 0;
  if (l->_data > 9) {
    carry = 1;
    l->_data %= 10;
  }
  l->_next = add(m ? m->_next : m, n ? n->_next : n, carry);
  
  return l;
}

// problem 5
template<typename T>
Node<T>* start_of_loop(Node<T>* head) {
  Node<T>* fast = head;
  Node<T>* slow = head;

  while (fast && fast->_next) {
    slow = slow->_next;
    fast = fast->_next->_next;
    if (slow == fast) 
      break;
  }

  if (!fast || !fast->_next)
    throw "No loop in the list";

  while (head != slow) {
    head = head->_next;
    slow = slow->_next;
  }
  return slow;
}

int main() {
  Node<int>* m = NULL; prepend(m, 5); prepend(m, 1); prepend(m, 3); // print_list(m);
  Node<int>* n = NULL; prepend(n, 1); prepend(n, 2); prepend(n, 9); prepend(n, 5); // print_list(n);
  
  cout << "Problem 4:" << endl;
  cout << "Test digits add" << endl;
  cout << "num 1: "; print_list(m);
  cout << "num 2: "; print_list(n);

  Node<int>* l = add(m,n,0);
  cout << "add: "; print_list(l);
  free_list(l);
  cout << endl;

  cout << "Problem 5:" << endl;
  cout << "Test finding start of the loop" << endl;
  Node<int>* tail = n;
  while (tail->_next) 
    tail = tail->_next;
  
  cout << "tail points to second elem in list" << endl;
  tail->_next = n->_next;
  cout << "start of loop: " << start_of_loop(n)->_data << " == 9" << endl;
  cout << "tail points to the head of list" << endl;
  tail->_next = n;
  cout << "start of loop: " << start_of_loop(n)->_data << " == 5" << endl;
  tail->_next = NULL;
  cout << endl;

  free_list(m);
  free_list(n);
  return 0;
}
